SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Bisection method</title>

</head>

Bisection method

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about searching zeros of continuous functions. For searching a finite sorted array, see <a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">binary search algorithm</a>. For the method of determining what software change caused a change in behavior, see <a href="Bisection_(software_engineering)" title="Bisection (software engineering)">Bisection (software engineering)</a>.</div>

In <a href="Mathematics" title="Mathematics">mathematics</a>, the bisection method is a <a href="Root-finding_algorithm" title="Root-finding algorithm">root-finding method</a> that applies to any <a href="Continuous_function" title="Continuous function">continuous function</a> for which one knows two values with opposite signs. The method consists of repeatedly <a href="Bisection" title="Bisection">bisecting</a> the <a href="Interval_(mathematics)" title="Interval (mathematics)">interval</a> defined by these values and then selecting the subinterval in which the function changes sign, and therefore must contain a <a href="Root_of_a_function" class="mw-redirect" title="Root of a function">root</a>. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods.<a href="#cite_note-1">[1]</a> The method is also called the interval halving method,<a href="#cite_note-2">[2]</a> the <a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">binary search method</a>,<a href="#cite_note-3">[3]</a> or the dichotomy method.<a href="#cite_note-4">[4]</a>

For <a href="Polynomial" title="Polynomial">polynomials</a>, more elaborate methods exist for testing the existence of a root in an interval (<a href="Descartes'_rule_of_signs" title="Descartes' rule of signs">Descartes' rule of signs</a>, <a href="Sturm's_theorem" title="Sturm's theorem">Sturm's theorem</a>, <a href="Budan's_theorem" title="Budan's theorem">Budan's theorem</a>). They allow extending the bisection method into efficient algorithms for finding all real roots of a polynomial; see <a href="Real-root_isolation" title="Real-root isolation">Real-root isolation</a>.

<div class="mw-heading mw-heading2"><h2 id="The_method">The method</h2></div>

The method is applicable for numerically solving the equation f(x) = 0 for the <a href="Real_number" title="Real number">real</a> variable x, where f is a <a href="Continuous_function" title="Continuous function">continuous function</a> defined on an interval [a, b] and where f(a) and f(b) have opposite signs. In this case a and b are said to bracket a root since, by the <a href="Intermediate_value_theorem" title="Intermediate value theorem">intermediate value theorem</a>, the continuous function f must have at least one root in the interval (a, b).

At each step the method divides the interval in two parts/halves by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. If c itself is a root then the process has succeeded and stops. Otherwise, there are now only two possibilities: either f(a) and f(c) have opposite signs and bracket a root, or f(c) and f(b) have opposite signs and bracket a root.<a href="#cite_note-5">[5]</a> The method selects the subinterval that is guaranteed to be a bracket as the new interval to be used in the next step. In this way an interval that contains a zero of f is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

Explicitly, if f(c)=0 then c may be taken as the solution and the process stops. Otherwise, if f(a) and f(c) have opposite signs, then the method sets c as the new value for b, and if f(b) and f(c) have opposite signs then the method sets c as the new a. In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Iteration_tasks">Iteration tasks</h3></div>

The input for the method is a continuous function f, an interval [a, b], and the function values f(a) and f(b). The function values are of opposite sign (there is at least one zero crossing within the interval). Each iteration performs these steps:

<ol><li>Calculate c, the midpoint of the interval, c = <style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>⁠a + b/2⁠.</li>

<li>Calculate the function value at the midpoint, f(c).</li>

<li>If convergence is satisfactory (that is, c − a is sufficiently small, or |f(c)| is sufficiently small), return c and stop iterating.</li>

<li>Examine the sign of f(c) and replace either (a, f(a)) or (b, f(b)) with (c, f(c)) so that there is a zero crossing within the new interval.</li></ol>

When implementing the method on a computer, there can be problems with finite precision, so there are often additional convergence tests or limits to the number of iterations. Although f is continuous, finite precision may preclude a function value ever being zero. For example, consider f(x) = cos x; there is no floating-point value approximating x = π/2 that gives exactly zero. Additionally, the difference between a and b is limited by the floating point precision; i.e., as the difference between a and b decreases, at some point the midpoint of [a, b] will be numerically identical to (within floating point precision of) either a or b.

<div class="mw-heading mw-heading3"><h3 id="Algorithm">Algorithm</h3></div>

The method may be written in <a href="Pseudocode" title="Pseudocode">pseudocode</a> as follows:<a href="#cite_note-7">[7]</a>

<pre>input: Function f,

endpoint values a, b,

tolerance TOL,

maximum iterations NMAX

conditions: a < b,

either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0

output: value which differs from a root of f(x) = 0 by less than TOL

N ← 1

while N ≤ NMAX do // limit iterations to prevent infinite loop

c ← (a + b)/2 // new midpoint

if f(c) = 0 or (b – a)/2 < TOL then // solution found

Output(c)

Stop

end if

N ← N + 1 // increment step counter

if sign(f(c)) = sign(f(a)) then a ← c else b ← c // new interval

end while

Output("Method failed.") // max number of steps exceeded

</pre>

<div class="mw-heading mw-heading3"><h3 id="Example:_Finding_the_root_of_a_polynomial">Example: Finding the root of a polynomial</h3></div>

Suppose that the bisection method is used to find a root of the polynomial

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=x^{3}-x-2\,.}</annotation>

</semantics>

</math><img src="./dda6541e379d29a5105142fe4bb2c2c744a1780c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.107ex; height:3.176ex;" alt="{\displaystyle f(x)=x^{3}-x-2\,.}" loading="lazy"></dd></dl>

First, two numbers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> have to be found such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(a)}</annotation>

</semantics>

</math><img src="./368cb4b81ba5754d7a354a4ce49c2f1084bdaace.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.318ex; height:2.843ex;" alt="{\displaystyle f(a)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(b)}</annotation>

</semantics>

</math><img src="./adbef9aaf500c30a3f107e5d7efb7a8627d3bba9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.085ex; height:2.843ex;" alt="{\displaystyle f(b)}" loading="lazy"> have opposite signs. For the above function, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=1}</annotation>

</semantics>

</math><img src="./6104442ed30596ef4d7795d3186273f68d796ea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;" alt="{\displaystyle a=1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b=2}</annotation>

</semantics>

</math><img src="./32584049ed5f72969777f89d69b74ee462875e82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.258ex; height:2.176ex;" alt="{\displaystyle b=2}" loading="lazy"> satisfy this criterion, as

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(1)=(1)^{3}-(1)-2=-2}</annotation>

</semantics>

</math><img src="./bda7fd98246bf3eb2f84426cdace5c5eaa449f68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.259ex; height:3.176ex;" alt="{\displaystyle f(1)=(1)^{3}-(1)-2=-2}" loading="lazy"></dd></dl>

and

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(2)=(2)^{3}-(2)-2=+4\,.}</annotation>

</semantics>

</math><img src="./bffe32eee9db434f3eaee198d1fd156b35f652cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.293ex; height:3.176ex;" alt="{\displaystyle f(2)=(2)^{3}-(2)-2=+4\,.}" loading="lazy"></dd></dl>

Because the function is continuous, there must be a root within the interval [1, 2].

In the first iteration, the end points of the interval which brackets the root are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}=1}</annotation>

</semantics>

</math><img src="./3f6489d2bc20b48a0f4acb8d102124ef02af3531.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.545ex; height:2.509ex;" alt="{\displaystyle a_{1}=1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{1}=2}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{1}=2}</annotation>

</semantics>

</math><img src="./d9dce469fa5b793e396ff97a28591a5b4f861687.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.313ex; height:2.509ex;" alt="{\displaystyle b_{1}=2}" loading="lazy">, so the midpoint is

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1}={\frac {2+1}{2}}=1.5}</annotation>

</semantics>

</math><img src="./6e89e0b48c6bbd36d82caa6c2e7007357d51726c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:17.231ex; height:5.176ex;" alt="{\displaystyle c_{1}={\frac {2+1}{2}}=1.5}" loading="lazy"></dd></dl>

The function value at the midpoint is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125}</annotation>

</semantics>

</math><img src="./dca0daa5e44fd7b783d41b26e4d14ba8cc359f64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.91ex; height:3.176ex;" alt="{\displaystyle f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125}" loading="lazy">. Because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(c_{1})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(c_{1})}</annotation>

</semantics>

</math><img src="./01266cee93820a85485dd3381c9e6d33e5665ddd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.149ex; height:2.843ex;" alt="{\displaystyle f(c_{1})}" loading="lazy"> is negative, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=1}</annotation>

</semantics>

</math><img src="./6104442ed30596ef4d7795d3186273f68d796ea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;" alt="{\displaystyle a=1}" loading="lazy"> is replaced with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=1.5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=1.5}</annotation>

</semantics>

</math><img src="./af32edb292a5728cbf261026dfe9b23bfa2f2bc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.3ex; height:2.176ex;" alt="{\displaystyle a=1.5}" loading="lazy"> for the next iteration to ensure that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(a)}</annotation>

</semantics>

</math><img src="./368cb4b81ba5754d7a354a4ce49c2f1084bdaace.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.318ex; height:2.843ex;" alt="{\displaystyle f(a)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(b)}</annotation>

</semantics>

</math><img src="./adbef9aaf500c30a3f107e5d7efb7a8627d3bba9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.085ex; height:2.843ex;" alt="{\displaystyle f(b)}" loading="lazy"> have opposite signs. As this continues, the interval between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> will become increasingly smaller, converging on the root of the function. See this happen in the table below.

<th>Iteration</th>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n}}</annotation>

</semantics>

</math><img src="./790f9209748c2dca7ed7b81932c37c02af1dbc31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.448ex; height:2.009ex;" alt="{\displaystyle a_{n}}" loading="lazy"></th>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{n}}</annotation>

</semantics>

</math><img src="./28e2d72f6dd9375c8f1f59f1effd9b4e5492ac97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.216ex; height:2.509ex;" alt="{\displaystyle b_{n}}" loading="lazy"></th>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{n}}</annotation>

</semantics>

</math><img src="./9b7e944bcb1be88e9a6a940638f2adce0ec4211a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.225ex; height:2.009ex;" alt="{\displaystyle c_{n}}" loading="lazy"></th>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(c_{n})}</annotation>

</semantics>

</math><img src="./8ae672a02a58d1f0c14f77452aa024f80f981d43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.313ex; height:2.843ex;" alt="{\displaystyle f(c_{n})}" loading="lazy">

</th></tr>

<td>−0.125

</td></tr>

<td style="text-align: right;">1.6093750

</td></tr>

<td style="text-align: right;">0.6660156

</td></tr>

<td style="text-align: right;">0.2521973

</td></tr>

<td style="text-align: right;">0.0591125

</td></tr>

<td>−0.0340538

</td></tr>

<td style="text-align: right;">0.0122504

</td></tr>

<td>−0.0109712

</td></tr>

<td style="text-align: right;">0.0006222

</td></tr>

<td>−0.0051789

</td></tr>

<td>−0.0022794

</td></tr>

<td>−0.0008289

</td></tr>

<td>−0.0001034

</td></tr>

<td style="text-align: right;">0.0002594

</td></tr>

<td style="text-align: right;">0.0000780

</td></tr></tbody></table>

After 13 iterations, it becomes apparent that there is a convergence to about 1.521: a root for the polynomial.

<div class="mw-heading mw-heading2"><h2 id="Analysis">Analysis</h2></div>

The method is guaranteed to converge to a root of f if f is a <a href="Continuous_function" title="Continuous function">continuous function</a> on the interval [a, b] and f(a) and f(b) have opposite signs. The <a href="Approximation_error" title="Approximation error">absolute error</a> is halved at each step so the method <a href="Rate_of_convergence" title="Rate of convergence">converges linearly</a>. Specifically, if c1 = ⁠a+b/2⁠ is the midpoint of the initial interval, and cn is the midpoint of the interval in the nth step, then the difference between cn and a solution c is bounded by<a href="#cite_note-8">[8]</a>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |c_{n}-c|\leq {\frac {|b-a|}{2^{n}}}.}</annotation>

</semantics>

</math><img src="./c45012c4e7e782aee06204f7b6be4e46d9927ad8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:18.309ex; height:5.843ex;" alt="{\displaystyle |c_{n}-c|\leq {\frac {|b-a|}{2^{n}}}.}" loading="lazy"></dd></dl>

This formula can be used to determine, in advance, an upper bound on the number of iterations that the bisection method needs to converge to a root to within a certain tolerance.

The number n of iterations needed to achieve a required tolerance ε (that is, an error guaranteed to be at most ε), is bounded by

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)\right\rceil ,}</annotation>

</semantics>

</math><img src="./49e5a2a3fe9440369e68acffc54b3a377eaa79bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:24.809ex; height:4.843ex;" alt="{\displaystyle n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)\right\rceil ,}" loading="lazy"></dd></dl>

where the initial bracket size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{0}=|b-a|}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon _{0}=|b-a|}</annotation>

</semantics>

</math><img src="./a7def425d41692f7a4198c429df0823fdcb627ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.458ex; height:2.843ex;" alt="{\displaystyle \epsilon _{0}=|b-a|}" loading="lazy"> and the required bracket size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon \leq \epsilon _{0}.}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon \leq \epsilon _{0}.}</annotation>

</semantics>

</math><img src="./c2dd02359456fb884cd5166880fd2a0b9de7a908.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.688ex; height:2.343ex;" alt="{\displaystyle \epsilon \leq \epsilon _{0}.}" loading="lazy"> The main motivation to use the bisection method is that over the set of continuous functions, no other method can guarantee to produce an estimate cn to the solution c that in the worst case has an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"> absolute error with less than n1/2 iterations.<a href="#cite_note-:0-9">[9]</a> This is also true under several common assumptions on function f and the behaviour of the function in the neighbourhood of the root.<a href="#cite_note-:0-9">[9]</a><a href="#cite_note-10">[10]</a>

However, despite the bisection method being optimal with respect to worst case performance under absolute error criteria it is sub-optimal with respect to average performance under standard assumptions <a href="#cite_note-11">[11]</a><a href="#cite_note-12">[12]</a> as well as asymptotic performance.<a href="#cite_note-:1-13">[13]</a> Popular alternatives to the bisection method, such as the <a href="Secant_method" title="Secant method">secant method</a>, <a href="Ridders'_method" title="Ridders' method">Ridders' method</a> or <a href="Brent's_method" title="Brent's method">Brent's method</a> (amongst others), typically perform better since they trade-off worst case performance to achieve higher <a href="Rate_of_convergence" title="Rate of convergence">orders of convergence</a> to the root. And, a strict improvement to the bisection method can be achieved with a higher order of convergence without trading-off worst case performance with the <a href="ITP_Method" class="mw-redirect" title="ITP Method">ITP Method</a>.<a href="#cite_note-:1-13">[13]</a><a href="#cite_note-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Generalization_to_higher_dimensions">Generalization to higher dimensions</h2></div>

The bisection method has been generalized to multi-dimensional functions. Such methods are called generalized bisection methods.<a href="#cite_note-15">[15]</a><a href="#cite_note-16">[16]</a>

<div class="mw-heading mw-heading3"><h3 id="Methods_based_on_degree_computation">Methods based on degree computation</h3></div>

Some of these methods are based on computing the <a href="Topological_degree" class="mw-redirect" title="Topological degree">topological degree</a>, which for a bounded region <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega \subseteq \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega \subseteq \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./c2776d402b8e3ef34e3505d645b264f6dfb6a72e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.673ex; height:2.509ex;" alt="{\displaystyle \Omega \subseteq \mathbb {R} ^{n}}" loading="lazy"> and a differentiable function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./14708a3459e31d073fb8313d16cb761ea49ce2c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.623ex; height:2.676ex;" alt="{\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}" loading="lazy"> is defined as a sum over its roots:

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \deg(f,\Omega ):=\sum _{y\in f^{-1}(\mathbf {0} )}\operatorname {sgn} \det(Df(y))}</annotation>

</semantics>

</math><img src="./7135d654353110f905743d0be70026b1d7e4a6a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:35.326ex; height:6.343ex;" alt="{\displaystyle \deg(f,\Omega ):=\sum _{y\in f^{-1}(\mathbf {0} )}\operatorname {sgn} \det(Df(y))}" loading="lazy">,</dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Df(y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Df(y)}</annotation>

</semantics>

</math><img src="./5cd97d2408ef0c33f1e3343f185f178bba94d336.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.168ex; height:2.843ex;" alt="{\displaystyle Df(y)}" loading="lazy"> is the <a href="Jacobian_matrix" class="mw-redirect" title="Jacobian matrix">Jacobian matrix</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {0} =(0,0,...,0)^{T}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {0} =(0,0,...,0)^{T}}</annotation>

</semantics>

</math><img src="./ef7bbfde17c6cac34a3b015e4e764fb391b9b4a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.325ex; height:3.176ex;" alt="{\displaystyle \mathbf {0} =(0,0,...,0)^{T}}" loading="lazy">, and

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn}(x)={\begin{cases}1,&x>0\\0,&x=0\\-1,&x<0\\\end{cases}}}</annotation>

</semantics>

</math><img src="./58afc068414e63f08062e5c58fdd3da41e94716d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:23.957ex; height:8.509ex;" alt="{\displaystyle \operatorname {sgn}(x)={\begin{cases}1,&x>0\\0,&x=0\\-1,&x<0\\\end{cases}}}" loading="lazy"></dd></dl>

is the <a href="Sign_function" title="Sign function">sign function</a>.<a href="#cite_note-17">[17]</a> In order for a root to exist, it is sufficient that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \deg(f,\Omega )\neq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \deg(f,\Omega )\neq 0}</annotation>

</semantics>

</math><img src="./ad9e709ddbc8c6f01f1701a2529006395e617ffa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.548ex; height:2.843ex;" alt="{\displaystyle \deg(f,\Omega )\neq 0}" loading="lazy">, and this can be verified using a <a href="Surface_integral" title="Surface integral">surface integral</a> over the boundary of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy">.<a href="#cite_note-18">[18]</a>

<div class="mw-heading mw-heading3"><h3 id="Characteristic_bisection_method">Characteristic bisection method</h3></div>

The characteristic bisection method uses only the signs of a function in different points. Lef f be a function from Rd to Rd, for some integer d ≥ 2. A characteristic polyhedron<a href="#cite_note-19">[19]</a> (also called an admissible polygon)<a href="#cite_note-:2-20">[20]</a> of f is a <a href="Polytope" title="Polytope">polytope</a> in Rd, having 2d vertices, such that in each vertex v, the combination of signs of f(v) is unique and the <a href="Degree_of_a_continuous_mapping#Maps_from_closed_region" title="Degree of a continuous mapping">topological degree of f on its interior</a> is not zero (a necessary criterion to ensure the existence of a root).<a href="#cite_note-:3-21">[21]</a> For example, for d=2, a characteristic polyhedron of f is a <a href="Quadrilateral" title="Quadrilateral">quadrilateral</a> with vertices (say) A,B,C,D, such that:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn} f(A)=(-,-)}</annotation>

</semantics>

</math><img src="./8b8f6775dd903ab1658620b4ec5ce6d23da5dec9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.147ex; height:2.843ex;" alt="{\displaystyle \operatorname {sgn} f(A)=(-,-)}" loading="lazy">⁠, that is, f1(A)<0, f2(A)<0.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn} f(B)=(-,+)}</annotation>

</semantics>

</math><img src="./4492d38cb717f967a1d970295403c301c1057e12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.168ex; height:2.843ex;" alt="{\displaystyle \operatorname {sgn} f(B)=(-,+)}" loading="lazy">⁠, that is, f1(B)<0, f2(B)>0.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn} f(C)=(+,-)}</annotation>

</semantics>

</math><img src="./c7f695a331a66a03778392c132b2f6b0da9e9064.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.171ex; height:2.843ex;" alt="{\displaystyle \operatorname {sgn} f(C)=(+,-)}" loading="lazy">⁠, that is, f1(C)>0, f2(C)<0.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn} f(D)=(+,+)}</annotation>

</semantics>

</math><img src="./8de9e8c398732a1d9c7cdcf39b83bff2fefd562f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.328ex; height:2.843ex;" alt="{\displaystyle \operatorname {sgn} f(D)=(+,+)}" loading="lazy">⁠, that is, f1(D)>0, f2(D)>0.</li></ul>

A proper edge of a characteristic polygon is an edge between a pair of vertices, such that the sign vector differs by only a single sign. In the above example, the proper edges of the characteristic quadrilateral are AB, AC, BD and CD. A diagonal is a pair of vertices, such that the sign vector differs by all d signs. In the above example, the diagonals are AD and BC.

At each iteration, the algorithm picks a proper edge of the polyhedron (say, A—B), and computes the signs of f in its mid-point (say, M). Then it proceeds as follows:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn} f(M)=\operatorname {sgn}(A)}</annotation>

</semantics>

</math><img src="./1ce7130312ba739a649981195a4ad90e7e9bf8be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.311ex; height:2.843ex;" alt="{\displaystyle \operatorname {sgn} f(M)=\operatorname {sgn}(A)}" loading="lazy">⁠, then A is replaced by M, and we get a smaller characteristic polyhedron.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn} f(M)=\operatorname {sgn}(B)}</annotation>

</semantics>

</math><img src="./94c81e73204074661b48bee3c132e5159b68cc06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.331ex; height:2.843ex;" alt="{\displaystyle \operatorname {sgn} f(M)=\operatorname {sgn}(B)}" loading="lazy">⁠, then B is replaced by M, and we get a smaller characteristic polyhedron.</li>

<li>Else, we pick a new proper edge and try again.</li></ul>

Suppose the diameter (= length of longest proper edge) of the original characteristic polyhedron is D. Then, at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(D/\varepsilon )}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}(D/\varepsilon )}</annotation>

</semantics>

</math><img src="./eb01a9edf927cfe427c8a8fec5c009fed8d1eaa3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.005ex; height:2.843ex;" alt="{\displaystyle \log _{2}(D/\varepsilon )}" loading="lazy"> bisections of edges are required so that the diameter of the remaining polygon will be at most ε.<a href="#cite_note-:2-20">[20]</a>: 11, Lemma.4.7 If the topological degree of the initial polyhedron is not zero, then there is a procedure that can choose an edge such that the next polyhedron also has nonzero degree.<a href="#cite_note-:3-21">[21]</a><a href="#cite_note-22">[22]</a>

<ul><li><a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">Binary search algorithm</a></li>

<li><a href="Lehmer%E2%80%93Schur_algorithm" title="Lehmer–Schur algorithm">Lehmer–Schur algorithm</a>, generalization of the bisection method in the complex plane</li>

<li><a href="Nested_intervals" title="Nested intervals">Nested intervals</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFBurdenFaires1985">Burden & Faires 1985</a>, p. 31

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20130519092250/http://siber.cankaya.edu.tr/NumericalComputations/ceng375/node32.html">"Interval Halving (Bisection)"</a>. Archived from <a rel="nofollow" class="external text" href="http://siber.cankaya.edu.tr/NumericalComputations/ceng375/node32.html">the original</a> on 2013-05-19. Retrieved 2013-11-07.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFBurdenFaires1985">Burden & Faires 1985</a>, p. 28

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php/Dichotomy_method">"Dichotomy method - Encyclopedia of Mathematics"</a>. www.encyclopediaofmath.org. Retrieved 2015-12-21.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <a href="#CITEREFBurdenFaires1985">Burden & Faires 1985</a>, p. 28 for section

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFBurdenFaires1985">Burden & Faires 1985</a>, p. 29. This version recomputes the function values at each iteration rather than carrying them to the next iterations.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="#CITEREFBurdenFaires1985">Burden & Faires 1985</a>, p. 31, Theorem 2.1

</li>

<li id="cite_note-:0-9">^ <a href="#cite_ref-:0_9-0">a</a> <a href="#cite_ref-:0_9-1">b</a> <cite id="CITEREFSikorski1982" class="citation journal cs1">Sikorski, K. (1982-02-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01459080">"Bisection is optimal"</a>. Numerische Mathematik. 40 (1): 111–117. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01459080">10.1007/BF01459080</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0945-3245">0945-3245</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119952605">119952605</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFSikorski1985" class="citation journal cs1">Sikorski, K (1985-12-01). "Optimal solution of nonlinear equations". Journal of Complexity. 1 (2): 197–209. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0885-064X%2885%2990011-1">10.1016/0885-064X(85)90011-1</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0885-064X">0885-064X</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFGrafNovakPapageorgiou1989" class="citation journal cs1">Graf, Siegfried; Novak, Erich; Papageorgiou, Anargyros (1989-07-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01396051">"Bisection is not optimal on the average"</a>. Numerische Mathematik. 55 (4): 481–491. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01396051">10.1007/BF01396051</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0945-3245">0945-3245</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119546369">119546369</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFNovak1989" class="citation journal cs1">Novak, Erich (1989-12-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0885-064X%2889%2990022-8">"Average-case results for zero finding"</a>. Journal of Complexity. 5 (4): 489–501. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0885-064X%2889%2990022-8">10.1016/0885-064X(89)90022-8</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0885-064X">0885-064X</a>.</cite>

</li>

<li id="cite_note-:1-13">^ <a href="#cite_ref-:1_13-0">a</a> <a href="#cite_ref-:1_13-1">b</a> <cite id="CITEREFOliveiraTakahashi2020" class="citation journal cs1">Oliveira, I. F. D.; Takahashi, R. H. C. (2020-12-06). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3423597">"An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality"</a>. ACM Transactions on Mathematical Software. 47 (1): 5:1–5:24. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3423597">10.1145/3423597</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0098-3500">0098-3500</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:230586635">230586635</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFIvo2020" class="citation web cs1">Ivo, Oliveira (2020-12-14). <a rel="nofollow" class="external text" href="https://link.growkudos.com/1iwxps83474">"An Improved Bisection Method"</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3423597">10.1145/3423597</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:230586635">230586635</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFMourrainVrahatisYakoubsohn2002" class="citation journal cs1">Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C. (2002-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcom.2001.0636">"On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree"</a>. Journal of Complexity. 18 (2): 612–640. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcom.2001.0636">10.1006/jcom.2001.0636</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0885-064X">0885-064X</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFVrahatis2020" class="citation book cs1">Vrahatis, Michael N. (2020). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-40616-5_17">"Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions"</a>. In Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). Numerical Computations: Theory and Algorithms. Lecture Notes in Computer Science. Vol. 11974. Cham: Springer International Publishing. pp. 223–238. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-40616-5_17">10.1007/978-3-030-40616-5_17</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-40616-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:211160947">211160947</a>.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFPolymilisServiziTurchettiSkokos2003" class="citation journal cs1">Polymilis, C.; Servizi, G.; Turchetti, G.; Skokos, Ch.; Vrahatis, M. N. (May 2003). "Locating Periodic Orbits by Topological Degree Theory". Libration Point Orbits and Applications: 665–676. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/nlin/0211044">nlin/0211044</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2F9789812704849_0031">10.1142/9789812704849_0031</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-981-238-363-1</bdi>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFKearfott1979" class="citation journal cs1">Kearfott, Baker (1979-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01404868">"An efficient degree-computation method for a generalized method of bisection"</a>. Numerische Mathematik. 32 (2): 109–127. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01404868">10.1007/BF01404868</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0945-3245">0945-3245</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122058552">122058552</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFVrahatis1995" class="citation journal cs1">Vrahatis, Michael N. (1995-06-01). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S0021999185711199">"An Efficient Method for Locating and Computing Periodic Orbits of Nonlinear Mappings"</a>. Journal of Computational Physics. 119 (1): 105–119. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1995JCoPh.119..105V">1995JCoPh.119..105V</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcph.1995.1119">10.1006/jcph.1995.1119</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0021-9991">0021-9991</a>.</cite>

</li>

<li id="cite_note-:2-20">^ <a href="#cite_ref-:2_20-0">a</a> <a href="#cite_ref-:2_20-1">b</a> <cite id="CITEREFVrahatisIordanidis1986" class="citation journal cs1">Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01389620">"A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations"</a>. Numerische Mathematik. 49 (2): 123–138. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01389620">10.1007/BF01389620</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0945-3245">0945-3245</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:121771945">121771945</a>.</cite>

</li>

<li id="cite_note-:3-21">^ <a href="#cite_ref-:3_21-0">a</a> <a href="#cite_ref-:3_21-1">b</a> <cite id="CITEREFVrahatisPerdiouKalantonisPerdios2001" class="citation journal cs1">Vrahatis, M.N.; Perdiou, A.E.; Kalantonis, V.S.; Perdios, E.A.; Papadakis, K.; Prosmiti, R.; Farantos, S.C. (July 2001). "Application of the Characteristic Bisection Method for locating and computing periodic orbits in molecular systems". Computer Physics Communications. 138 (1): 53–68. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2001CoPhC.138...53V">2001CoPhC.138...53V</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0010-4655%2801%2900190-4">10.1016/S0010-4655(01)00190-4</a>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFVrahatis1988" class="citation journal cs1">Vrahatis, Michael N. (December 1988). "Solving systems of nonlinear equations using the nonzero value of the topological degree". ACM Transactions on Mathematical Software. 14 (4): 312–329. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F50063.214384">10.1145/50063.214384</a>.</cite>

</li>

</ol></div>

<ul><li><cite id="CITEREFBurdenFaires1985" class="citation cs2">Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", <a rel="nofollow" class="external text" href="https://archive.org/details/numericalanalys00burd">Numerical Analysis</a> (3rd ed.), PWS Publishers, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-87150-857-5</bdi></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite class="citation cs2">Corliss, George (1977), "Which root does the bisection algorithm find?", SIAM Review, 19 (2): 325–327, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1019044">10.1137/1019044</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7200">1095-7200</a></cite></li>

<li><cite class="citation cs2">Kaw, Autar; Kalu, Egwu (2008), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090413123941/http://numericalmethods.eng.usf.edu/topics/textbook_index.html">Numerical Methods with Applications</a> (1st ed.), archived from <a rel="nofollow" class="external text" href="http://numericalmethods.eng.usf.edu/topics/textbook_index.html">the original</a> on 2009-04-13</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikiversity has learning resources about <a href="https://en.wikiversity.org/wiki/The_bisection_method" class="extiw external" title="v:The bisection method">The bisection method</a></div></div>

</div>

<div class="side-box-text plainlist">The Wikibook <a href="https://en.wikibooks.org/wiki/Numerical_Methods" class="extiw external" title="wikibooks:Numerical Methods">Numerical Methods</a> has a page on the topic of: <a href="https://en.wikibooks.org/wiki/Numerical_Methods/Equation_Solving" class="extiw external" title="wikibooks:Numerical Methods/Equation Solving">Equation Solving</a></div></div>

</div>

<ul><li><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/Bisection.html">"Bisection"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060901073129/http://numericalmethods.eng.usf.edu/topics/bisection_method.html">Bisection Method</a> Notes, PPT, Mathcad, Maple, Matlab, Mathematica from <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060906070428/http://numericalmethods.eng.usf.edu/">Holistic Numerical Methods Institute</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Root-finding_algorithms311" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Root-finding_algorithms311" style="font-size:114%;margin:0 4em"><a href="Root-finding_algorithm" title="Root-finding algorithm">Root-finding algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Root-finding_algorithm#Bracketing_methods" title="Root-finding algorithm">Bracketing (no derivative)</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul>

<li><a href="Regula_falsi" title="Regula falsi">Regula falsi</a></li>

<li><a href="ITP_method" title="ITP method">ITP method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Householder's_method" title="Householder's method">Householder</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method" title="Newton's method">Newton's method</a></li>

<li><a href="Halley's_method" title="Halley's method">Halley's method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi-Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Broyden's_method" title="Broyden's method">Broyden's method</a></li>

<li><a href="Secant_method" title="Secant method">Secant method</a></li>

<li><a href="Newton%E2%80%93Krylov_method" title="Newton–Krylov method">Newton–Krylov method</a></li>

<li><a href="Steffensen's_method" title="Steffensen's method">Steffensen's method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Root-finding_algorithm#Combinationations_of_methods" title="Root-finding algorithm">Hybrid methods</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Brent's_method" title="Brent's method">Brent's method</a></li>

<li><a href="Ridders'_method" title="Ridders' method">Ridders' method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Polynomial_root-finding_algorithms" class="mw-redirect" title="Polynomial root-finding algorithms">Polynomial methods</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Aberth_method" title="Aberth method">Aberth method</a></li>

<li><a href="Bairstow's_method" title="Bairstow's method">Bairstow's method</a></li>

<li><a href="Bernoulli's_method" title="Bernoulli's method">Bernoulli's method</a></li>

<li><a href="Durand%E2%80%93Kerner_method" title="Durand–Kerner method">Durand–Kerner method</a></li>

<li><a href="Graeffe's_method" title="Graeffe's method">Graeffe's method</a></li>

<li><a href="Jenkins%E2%80%93Traub_algorithm" title="Jenkins–Traub algorithm">Jenkins–Traub algorithm</a></li>

<li><a href="Lehmer%E2%80%93Schur_algorithm" title="Lehmer–Schur algorithm">Lehmer–Schur algorithm</a></li>

<li><a href="Laguerre's_method" title="Laguerre's method">Laguerre's method</a></li>

<li><a href="Splitting_circle_method" title="Splitting circle method">Splitting circle method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other methods</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Fixed-point_iteration" title="Fixed-point iteration">Fixed-point iteration</a></li>

<li><a href="Inverse_quadratic_interpolation" title="Inverse quadratic interpolation">Inverse quadratic interpolation</a></li>

<li><a href="Muller's_method" title="Muller's method">Muller's method</a></li>

<li><a href="Sidi's_generalized_secant_method" title="Sidi's generalized secant method">Sidi's generalized secant method</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-15" href="https://en.wikipedia.org/wiki/?title=Bisection_method&oldid=1300587306">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>